import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

/**
 * Ý tưởng là, tổng lớn nhất khi từng tổng thành phần là lớn nhất.
 * Định nghĩa tổng thành phần như ví dụ
 * 1
 * 12 89
 * 99 1 2
 * Từ 1, thử chọn 12, kiểm tra max (12) = (12 + 99 > 12 +  1 ) = 111
 * 			 chọn 89, kiểm tra max (89) = 89 + 2 > 89 + 1 = 91
 * => CHọn 12, và đi xuống 99
 * Không được nhỉ...
 * Không được :(
 * 
 * @author TrinhNX
 *
 */
public class Euler018 {
	public static void main(String[] args) {
		// Calculate 2^1000 = 1024^100
		long start = System.currentTimeMillis();
		Euler018 main = new Euler018();
		final int MAX = 15;
		Integer[][] data = new Integer[MAX][MAX];
		main.initData(data, MAX);
		main.printData(data);
		for (int i = MAX - 1; i >= 1; i--) {
			main.combine(data[i-1], data[i]);
		}
		main.printData(data);
		System.out.println("Time: " + (System.currentTimeMillis() - start));
	}

	// Cach 1, dung brute force
	private void initData(Integer[][] a, final int n) {
		// Init it
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				a[i][j] = 0;
			}
		}
		// Add from file
		try {
			FileReader fr = new FileReader(new File("data" + File.separator + "euler018.txt"));
			BufferedReader br = new BufferedReader(fr);
			String line = "";
			int counter = 0;
			while ((line = br.readLine()) != null) {
				String[] split = line.split(" ");
				for (int i = 0; i < split.length; i++) {
					a[counter][i] = Integer.valueOf(split[i]);
				}
				counter = counter + 1;
			}
			br.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

	}

	private void printData(Integer[][] a) {
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a.length; j++) {
				System.out.print(a[i][j] + "\t");
			}
			System.out.println();
		}
	}

	/**
	 * Combine first + second, then update the first array :"<
	 * Assume: same length
	 * @param first
	 * @param second
	 * Ex :
	 * 1st:  4 5 6 0
	 * 2nd: 7 8 3 9
	 * => Output: 12 13 15
	 * 
	 */
	private void combine(Integer[] first, Integer[] second) {
		for (int i = 0; i < first.length; i++) {
			if (first[i] != 0) {
				first[i] = (first[i] + second[i]) > (first[i] + second[i + 1]) ? (first[i] + second[i])
						: (first[i] + second[i + 1]);
			}
		}
	}

}